/*
 * Copyright:  2018 smarabbit studio.
 *
 *  Licensed under the Confluent Community License; you may not use this file
 *  except in compliance with the License.  You may obtain a copy of the License at
 *
 *  http://www.confluent.io/confluent-community-license
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
 *  WARRANTIES OF ANY KIND, either express or implied.  See the License for the
 *  specific language governing permissions and limitations under the License.
 *
 *  @作   者： 黄开晖 (117227773@qq.com)
 *  @日   期: 2019年12月2日
 */
package com.massyframework.beanskin.util.sorting.graph;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Vector;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.function.Predicate;
import java.util.stream.Collectors;

/**
 * {@link GraphMatrix},邻接矩阵实现图的算法
 * 
 * @author huangkh
 *
 */
final class GraphMatrix<T> implements Graph<T> {

	private int vertexNumber; // 当前顶点数量
	private int edgeNumber; // 当前边的数量
	private Vector<Vertex<T>> vertexs; // 顶点集合
	private Vector<Vector<Edge>> edges; // 边的集合（邻接矩阵）
	private Map<T, Integer> dataMap; // 顶点的data和顶点在数组中的pos映射表

	/**
	 * 创建一个新实例
	 */
	public GraphMatrix() {
		this.vertexNumber = 0;
		this.edgeNumber = 0;
		this.vertexs = new Vector<Vertex<T>>();
		this.edges = new Vector<Vector<Edge>>();
		this.dataMap = new HashMap<T, Integer>();
	}

	@Override
	public int vertexNumber() {
		return this.vertexNumber;
	}

	@Override
	public boolean exist(T data) {
		if (data == null)
			return false;
		return this.dataMap.containsKey(data);
	}

	@Override
	public boolean insert(T data) {
		if (this.dataMap.containsKey(data))
			return false;
		for (int i = 0; i < this.vertexNumber; i++) {
			this.edges.get(i).add(null);
		}
		this.vertexNumber++;

		Vector<Edge> vector = new Vector<Edge>();
		for (int i = 0; i < this.vertexNumber; i++) {
			vector.add(null);
		}
		this.edges.add(vector);

		this.vertexs.add(new Vertex<T>(data));
		this.dataMap.put(data, this.vertexNumber - 1);
		return true;
	}

	@Override
	public Vertex<T> remove(T data) {
		Integer pos = this.dataMap.get(data);
		if (pos == null)
			return null;

		for (int i = 0; i < this.vertexNumber; i++) {
			if (exists(pos, i)) {
				// 顶点i的入度减1
				Vertex<T> vector = this.vertexs.get(i);
				vector.setInDegree(vector.getInDegree() - 1);
			}
		}

		// 删除边
		int i1 = pos;
		this.edges.remove(i1);
		this.vertexNumber--;

		// 删除顶点
		Vertex<T> vector = this.vertexs.get(i1);
		this.vertexs.remove(i1);

		// 删除第i列
		for (int i = 0; i < this.vertexNumber; i++) {
			if (exists(i, pos)) {
				// 顶点出度减1
				Vertex<T> tmp = this.vertexs.get(i);
				tmp.setOutDegree(tmp.getOutDegree() - 1);
			}
			// 删除所有pos->i的边
			Vector<Edge> tmp =this.edges.get(i);
			tmp.remove(i1);
		}

		// 重置data
		for (int i = 0; i < this.vertexNumber; i++) {
			this.dataMap.put(this.vertexs.get(i).getData(), i);
		}
		return vector;
	}
	
	

	@Override
	public List<T> remove(Predicate<Vertex<T>> filter) {
		List<T> result = this.vertexs.stream()
				.filter(filter)
				.map( vertex -> vertex.getData())
				.collect(Collectors.toList());
		for (T data: result) {
			this.remove(data);
		}
				
		return result;
	}

	@Override
	public Vertex<T> find(T data) {
		Integer i = this.dataMap.get(data);
		if (i == null)
			return null;
		return this.vertexs.get(i);
	}

	@Override
	public int edgeNumber() {
		return this.edgeNumber;
	}

	@Override
	public boolean exist(T data1, T data2) {
		return find(data1, data2) != null;
	}

	@Override
	public boolean insert(T data1, T data2, Edge edge) {

		Integer i = this.dataMap.get(data1);
		Integer j = this.dataMap.get(data2);
		if (i == null || j == null)
			return false;

		if (!exists(i, j)) {
			this.edges.get(i).set(j, edge);
			++this.edgeNumber;

			Vertex<T> vector = this.vertexs.get(i);
			vector.setOutDegree(vector.getOutDegree() + 1);

			vector = this.vertexs.get(j);
			vector.setInDegree(vector.getInDegree() + 1);
		}
		return true;
	}

	@Override
	public Edge remove(T data1, T data2) {
		Integer i = this.dataMap.get(data1);
		Integer j = this.dataMap.get(data2);

		if (i == null || j == null || !exists(i, j))
			return null;

		Edge edge = this.edges.get(i).get(j);
		this.edges.get(i).set(j, null);
		--this.edgeNumber;

		Vertex<T> vector = this.vertexs.get(i);
		vector.setOutDegree(vector.getOutDegree() - 1);

		vector = this.vertexs.get(j);
		vector.setInDegree(vector.getInDegree() - 1);

		return edge;
	}

	@Override
	public Edge find(T data1, T data2) {
		Integer i = this.dataMap.get(data1);
		Integer j = this.dataMap.get(data2);
		if (i == null || j == null || !exists(i, j))
			return null;
		return this.edges.get(i).get(j);
	}

	@Override
	public void bfs(T data, Function<T> function) {
		Integer i = this.dataMap.get(data);
		if (i == null)
			return;

		reset();

		AtomicInteger clock = new AtomicInteger(0);
		int v = i;
		do {
			if (status(v) == VertexStatus.UNDISCOVERED) {
				this.doBFS(v, clock, function);
			}
		} while (i != (v = (++v % this.vertexNumber)));

	}
	
	public Vertex<T> getVertex(int i){
		if (i>-1 && i<this.vertexNumber) {
			return this.vertexs.get(i);
		}
		return null;
	}

	private void doBFS(int i, AtomicInteger clock, Function<T> function) {
		Queue<Integer> queue = new LinkedList<Integer>();
		function.discover(this.vertexs.get(i));
		this.vertexs.get(i).setStatus(VertexStatus.DISCOVERED);
		queue.add(i);

		while (!queue.isEmpty()) {
			i = queue.poll();// 取出对首顶点v
			this.vertexs.get(i).setdTime(clock.addAndGet(1));// v顶点的时钟加1

			for (int u = firstNeighbor(i); -1 < u; u = nextNeighbor(i, u)) {
				if (status(u) == VertexStatus.UNDISCOVERED) {
					Vertex<T> vertex = this.vertexs.get(u);
					function.discover(vertex);
					vertex.setStatus(VertexStatus.DISCOVERED);
					queue.add(u);
					this.edges.get(i).get(u).setType(EdgeType.TREE);
					vertex.setParent(i);
				} else {
					this.edges.get(i).get(u).setType(EdgeType.CROSS);
				}
			}
			function.visit(this.vertexs.get(i));
			this.vertexs.get(i).setStatus(VertexStatus.VISITED);
		}
	}

	@Override
	public void dfs(T data, Function<T> function) {
		Integer i = this.dataMap.get(data);
		if (i == null)
			return;
		reset();
		AtomicInteger clock = new AtomicInteger(0);
		int v = i;

		do {
			if (status(v) == VertexStatus.UNDISCOVERED) {
				doDFS(v, clock, function);
			}
		} while (i != (v = (++v % this.vertexNumber)));

	}
	
	private void doDFS(int i, AtomicInteger clock, Function<T> function) {
        Vertex<T> vertex = this.vertexs.get(i);
        vertex.setdTime(clock.addAndGet(1));
        function.discover(vertex);//发现顶点
        vertex.setStatus(VertexStatus.DISCOVERED);
        for(int j = firstNeighbor(i); -1 < j; j=nextNeighbor(i,j)){
            if(status(j) == VertexStatus.UNDISCOVERED){
                this.edges.get(i).get(j).setType(EdgeType.TREE);
                this.vertexs.get(j).setParent(i);
                doDFS(j,clock,function);
            }else if(status(j) == VertexStatus.DISCOVERED){
                this.edges.get(i).get(j).setType(EdgeType.BACKWARD);
            }else {
                this.edges.get(i).get(j).setType(dTime(i)<dTime(j)?EdgeType.FORWARD:EdgeType.CROSS);
            }
        }
        function.visit(vertex);
        vertex.setStatus(VertexStatus.VISITED);
        vertex.setfTime(clock.addAndGet(1));
    }

	/**
	 * 重置顶点和边
	 */
	private void reset() {
		for (int i = 0; i < this.vertexNumber; i++) {
			Vertex<T> vertex = this.vertexs.get(i);
			vertex.setStatus(VertexStatus.UNDISCOVERED);
			vertex.setdTime(-1);
			vertex.setfTime(-1);
			vertex.setParent(-1);
			vertex.setPriority(Integer.MAX_VALUE);
			for (int j = 0; j < this.vertexNumber; ++j) {
				if (exists(i, j)) {
					this.edges.get(i).get(j).setType(EdgeType.UNKNOWN);
				}
			}
		}
	}

	/**
	 * 首个相邻的顶点
	 * 
	 * @param i 顶点位置
	 * @return {@link int},指定顶点的第一个相邻顶点
	 */
	private int firstNeighbor(int i) {
		return nextNeighbor(i, this.vertexNumber);
	}

	/**
	 * 下一个相邻的顶点
	 * 
	 * @param i 顶点位置
	 * @param j 上一个相邻顶点位置
	 * @return {@link int},顶点i的下一个相邻顶点位置
	 */
	private int nextNeighbor(int i, int j) {
		while ((-1 < j) && (!exists(i, --j)))
			;
		return j;
	}

	/**
	 * 是否存在顶点i到顶点j的有向边
	 * 
	 * @param i 顶点i
	 * @param j 顶点j
	 * @return {@link boolean},返回{@code true}表示有，否则返回{@code false}
	 */
	private boolean exists(int i, int j) {
		if ((i <0) || (i >= this.vertexNumber)) return false;
		if ((j <0) || (j >= this.vertexNumber)) return false;
		
		Vector<Edge> vector = this.edges.get(i);
		return vector == null ?  false : vector.get(j) != null;
	}

	
	/**
	 * 顶点i的状态
	 * 
	 * @param i 顶点i
	 * @return {@link VertexStatus},顶点状态
	 */
	private VertexStatus status(int i) {
		return this.vertexs.get(i).getStatus();
	}

	/**
	 * 
	 * @param i
	 * @return
	 */
	private int dTime(int i) {
		return this.vertexs.get(i).getdTime();
	}

}
